package leetcode.all;

import datastruct.tree.TreeNode;

public class Solution110 {

    /**
     * 判断一棵树是否平衡二叉树，即每个节点得左右子树高度差不超过1
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int[] res = balanceAndHeight(root);
        return res[0]==1;
    }

    /**
     * 返回值[是否平衡，本节点高度]
     * @param node
     * @return
     */
    public int[] balanceAndHeight(TreeNode node){
        if(node==null) return new int[]{1,0};
        int[] left = balanceAndHeight(node.left);
        int[] right = balanceAndHeight(node.right);
        boolean flag = left[0]==1&&right[0]==1&&Math.abs(left[1]-right[1])<=1;
        int h = 1 + Math.max(left[1],right[1]);
        return new int[]{flag?1:-1,h};
    }

}
